package com.example.leetcode.StackMiddle;

import java.util.Stack;

public class A_索引处的解码字符串 {

    public static void main(String[] args) {
        /*String[] split = "123ad".split("");
        System.out.println("12".substring(0,0).equals(""));
        System.out.println(Pattern.matches("[2-9]",""));
        for (int i = 0; i < split.length; i++) {
            System.out.println(split[i]);
        }*/
        //String res = new Solution().decodeAtIndex("leet2code3", 10);
        //String res = new Solution().decodeAtIndex("a2345678999999999999999", 1);
        //String res = new Solution().decodeAtIndex("abc", 1);
        //String res = new Solution().decodeAtIndex("ha22", 5);
        //String res = new Solution().decodeAtIndex("a2b3c4d5e6f7g8h9",41);
        //String res = new Solution().decodeAtIndex("a23",6);
        //String res = new Solution().decodeAtIndex("a2b3c4d5e6f7g8h9",40);
        //String res = new Solution().decodeAtIndex("a2b3c4d5e6f7g8h9",623529);
        //String res = new Solution().decodeAtIndex("h5xk8ar9s222v93y22w2",311373); //h
        //String res = new Solution().decodeAtIndex("vk6u5xhq9v",554);
        String res = new Solution2().decodeAtIndex("czjkk9elaqwiz7s6kgvl4gjixan3ky7jfdg3kyop3husw3fm289thisef8blt7a7zr5v5lhxqpntenvxnmlq7l34ay3jaayikjps", 768077956);
        System.out.println(res);

    }
}

/*
 *思路一: 每遇到一个 数字,就建立个IndexString保存这个数字加倍后的长度(逆向工作法)
 */
class Solution {
    public String decodeAtIndex(String S, int K) {
        long k = (long) K;
        Stack<IndexString> indexStringStack = new Stack<>();
        String[] strings = S.split("");
        int startIndex = 0;
        for (int i = 0; i < strings.length; i++) {
            boolean digit = Character.isDigit(S.charAt(i));
            if (digit) {
                int multiple = Integer.parseInt(strings[i]);
                String extraString = S.substring(startIndex, i);
                startIndex = i + 1;
                long previousLength;
                if (indexStringStack.size() == 0) {
                    previousLength = 0;
                } else {
                    previousLength = indexStringStack.peek().getLength();
                }
                long thisLength = (previousLength + extraString.length()) * multiple;
                IndexString indexString = new IndexString(multiple, extraString, thisLength);
                indexStringStack.push(indexString);
                if (k <= thisLength) {
                    break;
                }
            } else if (i == strings.length - 1) {
                System.out.println("----");
                //最后一个 不是数字结尾
                int c = (int) (k - startIndex);
                return S.substring(c - 1, c);
            }
        }
        for (IndexString indexString : indexStringStack) {
            System.out.println(indexString);
        }
        if (indexStringStack.peek().getLength() >= K) {
            while (!indexStringStack.isEmpty()) {
                IndexString indexString = indexStringStack.pop();
                if (indexStringStack.isEmpty()) {

                    long thisLength = indexString.getLength();
                    int multiple = indexString.getMultiple();
                    long itemLength = thisLength / multiple;
                    k = k % itemLength;
                    if (k == 0) k = itemLength;
                    int c = (int) k;
                    return indexString.getExtraString().substring(c - 1, c);
                } else {
                    long previousLength = indexStringStack.peek().getLength();
                    long thisLength = indexString.getLength();
                    int multiple = indexString.getMultiple();
                    long itemLength = thisLength / multiple;
                    k = k % itemLength;
                    if (k == 0) {
                        k = itemLength;
                    }

                    if (k > previousLength) {
                        int c = (int) (k - previousLength);
                        return indexString.getExtraString().substring(c - 1, c);
                    }
                }

            }
        }
        return "";
    }

}

class IndexString {
    private int multiple;
    private String extraString;
    private long length;

    public IndexString(int multiple, String extraString, long length) {
        this.multiple = multiple;
        this.extraString = extraString;
        this.length = length;
    }

    public int getMultiple() {
        return multiple;
    }

    public void setMultiple(int multiple) {
        this.multiple = multiple;
    }

    public String getExtraString() {
        return extraString;
    }

    public void setExtraString(String extraString) {
        this.extraString = extraString;
    }

    public long getLength() {
        return length;
    }

    public void setLength(int length) {
        this.length = length;
    }

    @Override
    public String toString() {
        return "IndexString{" +
                "multiple=" + multiple +
                ", extraString='" + extraString + '\'' +
                ", length=" + length +
                '}';
    }
}
/*
* 思路2 :逆向工作法
 */
class Solution2 {
    public String decodeAtIndex(String S, int K) {
        long size = 0;
        int N = S.length();

        // Find size = length of decoded string
        int end=-1;
        for (int i = 0; i < N; ++i) {
            char c = S.charAt(i);
            if (Character.isDigit(c))
                size *= c - '0';
            else
                size++;
            if(size>K){end=i;break;}
        }
        if (end==-1) end=N-1;
        for (int i = end; i >= 0; --i) {
            char c = S.charAt(i);
            K %= size;
            if (K == 0 && Character.isLetter(c))
                return Character.toString(c);

            if (Character.isDigit(c))
                size /= c - '0';
            else
                size--;
        }

        throw null;
    }
}